{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Append K Integers With Minimal Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimalKSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #向数组中追加 K 个整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> 。请你向 <code>nums</code> 中追加 <code>k</code> 个 <strong>未</strong> 出现在 <code>nums</code> 中的、<strong>互不相同</strong> 的 <strong>正</strong> 整数，并使结果数组的元素和 <strong>最小</strong> 。</p>\n",
    "\n",
    "<p>返回追加到 <code>nums</code> 中的 <code>k</code> 个整数之和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,4,25,10,25], k = 2\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。\n",
    "nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。\n",
    "所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [5,6], k = 6\n",
    "<strong>输出：</strong>25\n",
    "<strong>解释：</strong>在该解法中，向数组中追加的两个互不相同且未出现的正整数是 1 、2 、3 、4 、7 和 8 。\n",
    "nums 最终元素和为 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36 ，这是所有情况中的最小值。\n",
    "所以追加到数组中的两个整数之和是 1 + 2 + 3 + 4 + 7 + 8 = 25 ，所以返回 25 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [append-k-integers-with-minimal-sum](https://leetcode.cn/problems/append-k-integers-with-minimal-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [append-k-integers-with-minimal-sum](https://leetcode.cn/problems/append-k-integers-with-minimal-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,25,10,25]\\n2', '[5,6]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        sums = (k * k + k) // 2\n",
    "        flag = True\n",
    "        previous = 0\n",
    "        for i in nums:\n",
    "            if i == previous:\n",
    "                continue\n",
    "            if i <= k:\n",
    "                sums = sums + k - i + 1\n",
    "                k += 1 \n",
    "            else:\n",
    "                flag = False\n",
    "                break\n",
    "            previous = i\n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        x, ans = 0, 0\n",
    "        for i in nums:\n",
    "            if i > x:\n",
    "                if (n := i - x - 1) > 0:\n",
    "                    if n > k:\n",
    "                        ans += self.sum(x, x + k + 1)\n",
    "                        return ans\n",
    "                    else:\n",
    "                        k -= n\n",
    "                        ans += self.sum(x, i)\n",
    "                x = i\n",
    "\n",
    "        if k:\n",
    "            ans += self.sum(nums[-1], nums[-1] + k + 1)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def sum(self, a: int, b: int) -> int:\n",
    "        # range is (a, b)\n",
    "        if a >= b:\n",
    "            return 0\n",
    "        return (a + b) * (b - a - 1) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        arr = [0]+sorted(nums)+[10**9+10]\n",
    "        ans = 0\n",
    "        def cal(st, t):\n",
    "            return (st+st+t-1)*t//2\n",
    "        for i in range(1, len(arr)):\n",
    "            t = min(k, arr[i]-arr[i-1]-1)\n",
    "            if t<0:\n",
    "                t = 0\n",
    "            ans += cal(arr[i-1]+1, t)\n",
    "            k -= t\n",
    "    \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        arr = [0]+sorted(nums)+[10**9+10]\n",
    "        ans = 0\n",
    "        def cal(st, t):\n",
    "            return (st+st+t-1)*t//2\n",
    "        for i in range(1, len(arr)):\n",
    "            t = min(k, arr[i]-arr[i-1]-1)\n",
    "            if t<=0:\n",
    "                continue\n",
    "            ans += cal(arr[i-1]+1, t)\n",
    "            k -= t\n",
    "    \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        res = (k+1)*k//2\n",
    "        nums.sort()\n",
    "        prev = -1\n",
    "        for n in nums:\n",
    "            if n > k:\n",
    "                break\n",
    "            if n == prev:\n",
    "                continue\n",
    "            if n <= k:\n",
    "                res -= n\n",
    "                k += 1\n",
    "                res += k\n",
    "            prev = n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        ans_sum = 0\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        \n",
    "        # 处理左侧\n",
    "        if nums[0] > 1:\n",
    "            res = nums[0] - 1\n",
    "            if res < k:\n",
    "                # ans_sum += acc_add(0, nums[0])\n",
    "                ans_sum += (nums[0]) * res // 2 \n",
    "                k -= res\n",
    "            elif res >= k:\n",
    "                # ans_sum += acc_add(0, k + 1)\n",
    "                ans_sum += (k + 1) * k // 2\n",
    "                k = 0\n",
    "\n",
    "        # 处理中间段\n",
    "        if k != 0:\n",
    "            for i in range(1, len(nums)):\n",
    "                res = nums[i] - nums[i - 1] - 1\n",
    "                if 1 <= res <= k:\n",
    "                    # ans_sum += acc_add(nums[i - 1], nums[i])\n",
    "                    ans_sum += (nums[i - 1] + nums[i]) * res // 2 \n",
    "                    k -= res\n",
    "                elif res > k:\n",
    "                    # ans_sum += acc_add(nums[i - 1], nums[i - 1] + k + 1)\n",
    "                    ans_sum += (nums[i - 1] + nums[i - 1] + k + 1) * k // 2 \n",
    "                    k = 0\n",
    "                    break\n",
    "        # 处理右侧\n",
    "        if k != 0:\n",
    "            # ans_sum += acc_add(nums[-1], nums[-1] + k + 1)\n",
    "            ans_sum += (nums[-1] + nums[-1] + k + 1) * k // 2 \n",
    "\n",
    "        return ans_sum\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.append(0)\n",
    "        nums.sort()\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == nums[i - 1]: continue\n",
    "            area = nums[i] - nums[i - 1] - 1\n",
    "            if k >= area:\n",
    "                k -= area\n",
    "                ans += (nums[i] + nums[i - 1]) * (nums[i] - nums[i - 1] - 1) // 2\n",
    "            else:\n",
    "                ans += (nums[i - 1] + 1 + nums[i - 1] + k) * k // 2\n",
    "                k = 0\n",
    "            if k == 0:\n",
    "                break\n",
    "            \n",
    "        if k:\n",
    "            ans += (nums[-1] + 1 + nums[-1] + k) * k // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        ans_sum = 0\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        \n",
    "        # 处理左侧\n",
    "        if nums[0] > 1:\n",
    "            res = nums[0] - 1\n",
    "            if res < k:\n",
    "                ans_sum += (nums[0]) * res // 2 \n",
    "                k -= res\n",
    "            elif res >= k:\n",
    "                ans_sum += (k + 1) * k // 2\n",
    "                k = 0\n",
    "\n",
    "        # 处理中间段\n",
    "        if k != 0:\n",
    "            for i in range(1, len(nums)):\n",
    "                res = nums[i] - nums[i - 1] - 1\n",
    "                if 1 <= res <= k:\n",
    "                    ans_sum += (nums[i - 1] + nums[i]) * res // 2 \n",
    "                    k -= res\n",
    "                elif res > k:\n",
    "                    ans_sum += (nums[i - 1] + nums[i - 1] + k + 1) * k // 2 \n",
    "                    k = 0\n",
    "                    break\n",
    "        # 处理右侧\n",
    "        if k != 0:\n",
    "            ans_sum += (nums[-1] + nums[-1] + k + 1) * k // 2 \n",
    "\n",
    "        return ans_sum\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        temp = 0\n",
    "        sum1 = 0\n",
    "        for i in nums:\n",
    "            cha = i - temp - 1\n",
    "            if cha > k:\n",
    "                return int(sum1+ (temp+1+temp+k)*k / 2)\n",
    "            elif cha > 0:\n",
    "                k -= cha\n",
    "                sum1 += (temp+1+temp+cha)*cha / 2\n",
    "            temp = i\n",
    "        return int(sum1+ (temp+1+temp+k)*k / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "       nums.sort()\n",
    "       n = len(nums)\n",
    "       pre = 0\n",
    "       res = 0\n",
    "       for x in nums:\n",
    "          if x - pre <= 1:\n",
    "             pre = x\n",
    "             continue\n",
    "          first = pre + 1\n",
    "          last = min(x - 1, first + k - 1)\n",
    "          res += (first + last) * (last - first + 1) // 2\n",
    "          pre = x\n",
    "          k -= last - first + 1\n",
    "       first = nums[-1] + 1\n",
    "       last = first + k - 1\n",
    "       res += (first + last) * (last - first + 1) // 2\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.extend([0, int(2e9) + 1])\n",
    "        nums.sort()\n",
    "\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            offer = nums[i] - nums[i - 1] - 1\n",
    "            if offer > 0:\n",
    "                if offer < k:\n",
    "                    k -= offer\n",
    "                else:\n",
    "                    ans = (nums[i - 1] + k + 1) * (nums[i - 1] + k) // 2 - presum\n",
    "                    break\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                presum += nums[i]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 9 + 1\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        def total(l, r):\n",
    "            return (r + l - 1) * (r - l) >> 1\n",
    "\n",
    "        nums.extend((0, MX))\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for x, y in pairwise(nums):\n",
    "            x += 1\n",
    "            if y <= x:\n",
    "                continue\n",
    "            # 可加入的数字数量\n",
    "            add = min(k, y - x)\n",
    "            ans += total(x, x + add)\n",
    "            k -= add\n",
    "            if not k:\n",
    "                break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.extend([0, int(2e9) + 1])\n",
    "        nums.sort()\n",
    "\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            offer = nums[i] - nums[i - 1] - 1\n",
    "            if offer > 0:\n",
    "                if offer < k:\n",
    "                    k -= offer\n",
    "                else:\n",
    "                    ans = (nums[i - 1] + k + 1) * (nums[i - 1] + k) // 2 - presum\n",
    "                    break\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                presum += nums[i]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums += [0, 2e9 + 1]\n",
    "        nums.sort()\n",
    "\n",
    "        occupied = 0\n",
    "        res = 0\n",
    "        # compare joint two nums in list\n",
    "        for i in range(1, len(nums)):\n",
    "            vacant = nums[i] - nums[i - 1] - 1\n",
    "            if vacant > 0:\n",
    "                if vacant < k:\n",
    "                    k -= vacant # vacant space occupied\n",
    "                else:\n",
    "                    res = (1 + nums[i - 1] + k) * (nums[i - 1] + k) // 2 - occupied\n",
    "                    break\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                occupied += nums[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        nums.sort()         # 排序 【方便后续判断和去重】\n",
    "        \n",
    "        # 贪心地认为追加的k个整数为[1, k]，先直接求和\n",
    "        ans = k*(k+1)//2\n",
    "        \n",
    "        # 判断[1, k]与nums中的元素存在重复的情况，并对追加元素的最后一位（即追加的最大元素）做调整\n",
    "        last = k            # last记录追加的最后一个元素，暂时为k\n",
    "        pre = -1            # 上一个nums中的元素 【去重】\n",
    "        for num in nums:            # nums已有序，每次遍历得到当前最小值\n",
    "\n",
    "            if num == pre:          # 遇到多个重复的num，只调整一次last即可\n",
    "                continue\n",
    "\n",
    "            if num <= last:         # 当前num必与追加的元素存在重复\n",
    "                ans += last+1-num   # 考虑将（追加的）重复元素调整为last+1，避免与nums存在重复\n",
    "                last += 1           # last调整+1\n",
    "                pre = num           # 记录上一个num，方便去重\n",
    "\n",
    "            else:                   # 若当前num>last（num为遍历到的最小值）\n",
    "                return ans          # 则nums的后续元素均大于追加元素，无需再调整\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        nums.extend([0, inf])\n",
    "        nums.sort()\n",
    "        for x,y in pairwise(nums):\n",
    "            fill = y - x - 1\n",
    "            if fill <= 0:\n",
    "                continue\n",
    "            if fill >= k:\n",
    "                return ans + (x * 2 + 1 + k) * k // 2  # 等差数列求和\n",
    "            ans += (x + y) * fill // 2  # 填充 fill 个数：等差数列求和\n",
    "            k -= fill\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        start, ans= 0, 0\n",
    "        for num in nums:\n",
    "            intv = num - start -1\n",
    "            if intv <= 0:\n",
    "                start = num\n",
    "                continue\n",
    "            if intv <= k:\n",
    "                ans += (start + 1 + num - 1) * intv // 2\n",
    "                k -= intv\n",
    "                start = num\n",
    "            else:\n",
    "                ans += (start + 1 + start + k) * k // 2\n",
    "                k = 0\n",
    "            if k == 0:\n",
    "                break\n",
    "        if k > 0:\n",
    "            ans += (nums[-1] + 1 + nums[-1] + k) * k // 2\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        def total(l, r):\n",
    "            return (r + l - 1) * (r - l) >> 1\n",
    "\n",
    "        nums.append(0)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for x, y in pairwise(nums):\n",
    "            x += 1\n",
    "            if y <= x:\n",
    "                continue\n",
    "            # 可加入的数字数量\n",
    "            add = min(k, y - x)\n",
    "            ans += total(x, x + add)\n",
    "            k -= add\n",
    "            if not k:\n",
    "                return ans\n",
    "\n",
    "        left = nums[-1] + 1\n",
    "        ans += total(left, left + k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        maxv = 0\n",
    "        while i<n and k>0:\n",
    "            if i>0 and nums[i-1]==nums[i]:\n",
    "                i+=1\n",
    "                continue\n",
    "            if nums[i]-maxv-1>=k:\n",
    "                maxv += k\n",
    "                k=0\n",
    "                break\n",
    "            k-=nums[i]-maxv-1\n",
    "            res-=nums[i]\n",
    "            maxv = nums[i]\n",
    "            i+=1\n",
    "        if k>0:\n",
    "            maxv += k\n",
    "        res+=(maxv+1)*maxv//2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        nums = [0] + nums\n",
    "        n = len(nums)\n",
    "        s = 0\n",
    "        # print(f'{nums}')\n",
    "        for i in range(n - 1):\n",
    "            if nums[i + 1] > nums[i] + 1:\n",
    "                mx = min(nums[i + 1] - nums[i] - 1, k) # 1, 4\n",
    "                l = nums[i] + 1\n",
    "                s +=  l * mx + mx * (mx - 1) // 2\n",
    "                k -= mx\n",
    "                # print(f'{mx, k, s}')\n",
    "                if k == 0:\n",
    "                    return s\n",
    "        return s + (nums[-1] + 1) * k + k * (k - 1) // 2\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.extend([0, int(2e9) + 1]) #加入一头，一尾，作为起始标志位\n",
    "        nums.sort()\n",
    "\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            interval = nums[i] - nums[i - 1] - 1\n",
    "            if interval > 0:\n",
    "                if interval < k:\n",
    "                    k -= interval\n",
    "                else:\n",
    "                    ans = (nums[i - 1] + k + 1) * (nums[i - 1] + k) // 2 - presum #从1到当前位置的和 - 前缀和\n",
    "                    break\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                presum += nums[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.extend([0, int(2e9) + 1])\n",
    "        nums.sort()\n",
    "\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            offer = nums[i] - nums[i - 1] - 1\n",
    "            if offer > 0:\n",
    "                if offer < k:\n",
    "                    k -= offer\n",
    "                else:\n",
    "                    ans = (nums[i - 1] + k + 1) * (nums[i - 1] + k) // 2 - presum\n",
    "                    break\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                presum += nums[i]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        # s = set(nums)\n",
    "        # ans = 0\n",
    "        # maxValue = max(nums)\n",
    "        # for i in range(1, maxValue):\n",
    "        #     if i not in s:\n",
    "        #         ans += i \n",
    "        #         k -= 1\n",
    "        #     if k == 0:\n",
    "        #         break\n",
    "        # while k > 0:\n",
    "        #     ans += maxValue + k \n",
    "        #     k -= 1\n",
    "\n",
    "        nums.extend([0, int(2e9) + 1])\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        presum = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            offer = nums[i] - nums[i-1] - 1\n",
    "            if offer > 0:\n",
    "                if offer < k:\n",
    "                    k -= offer\n",
    "                else:\n",
    "                    ans = (nums[i - 1] + k + 1) * (nums[i - 1] + k) // 2 - presum\n",
    "                    break \n",
    "            if nums[i] != nums[i-1]:\n",
    "                presum += nums[i]\n",
    "\n",
    "        return ans\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.extend([0,inf])\n",
    "        nums = sorted(nums)\n",
    "        ans = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            while k >0:\n",
    "                start = nums[i]\n",
    "                end = nums[i+1]\n",
    "                if end-start<=1:\n",
    "                    i+=1\n",
    "                else:\n",
    "                    ans = ans + (start+end) * (end-start-1)//2 if end-start-1 < k else ans + (start * 2 + 1 + k) * k // 2\n",
    "                  #  res = res + list(range(start+1,end)) if end-start-1 < k else res + list(range(start+1,start+k+1))\n",
    "                    k-=(end-start-1)\n",
    "                    i+=1\n",
    "        return(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.extend([0, int(2e9) + 1])\n",
    "        nums.sort()\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            offer = nums[i] - nums[i - 1] - 1\n",
    "            if offer > 0:\n",
    "                if offer < k:\n",
    "                    k -= offer\n",
    "                else:\n",
    "                    ans = (nums[i - 1] + k + 1) * (nums[i - 1] + k) // 2 - presum\n",
    "                    break\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                presum += nums[i]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        l=1\n",
    "        r=nums[0]-1\n",
    "        if l<=r:\n",
    "            if r-l+1<=k:\n",
    "                ans+=(l+r)*(r-l+1)//2\n",
    "                k-=(r-l+1)\n",
    "            else:\n",
    "                ans+=(2*l+k-1)*k//2\n",
    "                return ans\n",
    "        for i in range(1,n):\n",
    "            \n",
    "            l=nums[i-1]+1\n",
    "            r=nums[i]-1\n",
    "            if l<=r :\n",
    "                if r-l+1<=k:\n",
    "                    ans+=(l+r)*(r-l+1)//2\n",
    "                    k-=(r-l+1)\n",
    "                else:\n",
    "                    ans+=(2*l+k-1)*k//2\n",
    "                    return ans\n",
    "        x=nums[-1]+1\n",
    "        ans+=(2*x+k-1)*k//2\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 9 + 1\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.extend((0, MX))\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for x, y in pairwise(nums):\n",
    "            x += 1\n",
    "            if y > x:\n",
    "                # 可加入的数字数量\n",
    "                add = min(k, y - x)\n",
    "                r = x + add\n",
    "                ans += (r + x - 1) * (r - x) >> 1\n",
    "                k -= add\n",
    "                if not k:\n",
    "                    break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.extend([0, inf])\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for x, y in pairwise(nums):\n",
    "            fill = y - x - 1\n",
    "            if fill <= 0:\n",
    "                continue\n",
    "            if fill >= k:\n",
    "                return ans + (x + 1 + x + k) * k // 2\n",
    "            ans += (x + y) * fill // 2\n",
    "            k -= fill"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        # s = set(nums)\n",
    "        # ans = 0\n",
    "        # maxValue = max(nums)\n",
    "        # for i in range(1, maxValue):\n",
    "        #     if i not in s:\n",
    "        #         ans += i \n",
    "        #         k -= 1\n",
    "        #     if k == 0:\n",
    "        #         break\n",
    "        # while k > 0:\n",
    "        #     ans += maxValue + k \n",
    "        #     k -= 1\n",
    "\n",
    "        nums.extend([0, int(2e9) + 1])\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        presum = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            offer = nums[i] - nums[i-1] - 1\n",
    "            if offer > 0:\n",
    "                if offer < k:\n",
    "                    k -= offer\n",
    "                else:\n",
    "                    ans = (nums[i - 1] + k + 1) * (nums[i - 1] + k) // 2 - presum\n",
    "                    break \n",
    "            if nums[i] != nums[i-1]:\n",
    "                presum += nums[i]\n",
    "\n",
    "        return ans\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\r\n",
    "        nums.extend([0,inf])\r\n",
    "        list1 = nums\r\n",
    "        list1.sort()\r\n",
    "        ans = 0\r\n",
    "        for i in range(len(list1)-1):\r\n",
    "            fill = list1[i+1] - list1[i] - 1\r\n",
    "            if fill <= 0:\r\n",
    "                continue\r\n",
    "            if fill >= k:\r\n",
    "                return ans +(list1[i]*2 + k + 1) * k // 2\r\n",
    "            ans += (list1[i]*2 + fill + 1) * fill // 2\r\n",
    "            k -= fill\r\n",
    "\r\n",
    "\r\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        nums.sort()         # 排序 【方便后续判断和去重】\n",
    "        \n",
    "        # 贪心地认为追加的k个整数为[1, k]，先直接求和\n",
    "        ans = k*(k+1)//2\n",
    "        \n",
    "        # 判断[1, k]与nums中的元素存在重复的情况，并对追加元素的最后一位（即追加的最大元素）做调整\n",
    "        last = k            # last记录追加的最后一个元素，暂时为k\n",
    "        pre = -1            # 上一个nums中的元素 【去重】\n",
    "        for num in nums:            # nums已有序，每次遍历得到当前最小值\n",
    "\n",
    "            if num == pre:          # 遇到多个重复的num，只调整一次last即可\n",
    "                continue\n",
    "\n",
    "            if num <= last:         # 当前num必与追加的元素存在重复\n",
    "                ans += last+1-num   # 考虑将（追加的）重复元素调整为last+1，避免与nums存在重复\n",
    "                last += 1           # last调整+1\n",
    "                pre = num           # 记录上一个num，方便去重\n",
    "\n",
    "            else:                   # 若当前num>last（num为遍历到的最小值）\n",
    "                return ans          # 则nums的后续元素均大于追加元素，无需再调整\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.append(0)\n",
    "        nums.append(inf)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        sum = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            now = nums[i]\n",
    "            coming = nums[i+1]\n",
    "            if now + 1 < coming:\n",
    "                cnt = coming - now - 1\n",
    "                if cnt > k:\n",
    "                    sum += (now + 1 + now + k) * k // 2\n",
    "                    return sum\n",
    "                else:\n",
    "                    sum += (now + 1 + now + cnt) * cnt // 2\n",
    "                    k = k - cnt\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        nums.extend([0, inf])  # 加入两个哨兵\n",
    "        nums.sort()\n",
    "        for x, y in pairwise(nums):\n",
    "            fill = y - x - 1  # 可以填充的数字个数\n",
    "            if fill <= 0:  # 没有可以填充的位置\n",
    "                continue\n",
    "            if fill >= k:  # 填充剩余的 k 个数\n",
    "                return ans + (x * 2 + 1 + k) * k // 2  # 等差数列求和\n",
    "            ans += (x + y) * fill // 2  # 填充 fill 个数：等差数列求和\n",
    "            k -= fill  # 更新剩余要填充的数字个数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        nums.extend([0, inf])  # 加入两个哨兵\n",
    "        nums.sort()\n",
    "        for x, y in pairwise(nums):\n",
    "            fill = y - x - 1  # 可以填充的数字个数\n",
    "            if fill <= 0:  # 没有可以填充的位置\n",
    "                continue\n",
    "            if fill >= k:  # 填充剩余的 k 个数\n",
    "                return ans + (x * 2 + 1 + k) * k // 2  # 等差数列求和\n",
    "            ans += (x + y) * fill // 2  # 填充 fill 个数：等差数列求和\n",
    "            k -= fill  # 更新剩余要填充的数字个数\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        # nums.sort()\n",
    "        # # print(nums)\n",
    "        # n = len(nums)\n",
    "        # res = idx = 0\n",
    "        # pre = 1\n",
    "        # for i in nums:\n",
    "        #     if pre < i:\n",
    "        #         if pre + k - 1 < i:\n",
    "        #             res += (2*pre+k-1) * k // 2\n",
    "        #             k = 0\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             gap = i - pre \n",
    "        #             res += (pre+i-1) * gap // 2 \n",
    "        #             k -= gap\n",
    "        #     pre = i + 1\n",
    "        #     # print(pre, i, res)\n",
    "        # return res+(pre*2+k-1) * k // 2 if k else res\n",
    "\n",
    "        # -----------------------------\n",
    "        res = 0\n",
    "        nums.extend([0, inf])\n",
    "        nums.sort()\n",
    "        for x, y in pairwise(nums):\n",
    "            fill = y - x - 1 \n",
    "            if fill <= 0:\n",
    "                continue \n",
    "            if fill >= k:\n",
    "                return res + (2*x+1+k) * k // 2 \n",
    "            res += (x+y) * fill // 2 \n",
    "            k -= fill"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        nums.extend([0, inf])  # 加入两个哨兵\n",
    "        nums.sort()\n",
    "        for x, y in pairwise(nums): #pairwise 获取连续的重叠对\n",
    "            fill = y - x - 1  # 可以填充的数字个数\n",
    "            if fill <= 0:  # 没有可以填充的位置\n",
    "                continue\n",
    "            if fill >= k:  # 填充剩余的 k 个数\n",
    "                return ans + (x * 2 + 1 + k) * k // 2  # 等差数列求和\n",
    "            ans += (x + y) * fill // 2  # 填充 fill 个数：等差数列求和\n",
    "            k -= fill  # 更新剩余要填充的数字个数\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        nums.append(0)\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            x, y = nums[i-1], nums[i]\n",
    "            if y <= x+1:\n",
    "                continue\n",
    "            if not k:\n",
    "                break\n",
    "            start = x+1\n",
    "            end = y-1\n",
    "            cnt = end-start+1\n",
    "            if cnt > k:\n",
    "                cnt = k\n",
    "            k -= cnt\n",
    "            end = start + cnt - 1\n",
    "            ans += cnt*(start+end)//2\n",
    "        if k:\n",
    "            start = nums[-1] + 1\n",
    "            end = nums[-1] + k\n",
    "            cnt = k\n",
    "            ans += cnt * (start + end) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "    hq = []\n",
    "    for n in nums:\n",
    "      heapq.heappush(hq, n)\n",
    "    ret, s = 0, 1\n",
    "    while k > 0:\n",
    "      if len(hq) > 0:\n",
    "        n = heapq.heappop(hq)\n",
    "        if n > s:\n",
    "          e = min(n - 1, s + k - 1)\n",
    "          # print(f\"calc s {s} e {e} n {n}\")\n",
    "          c = e - s + 1\n",
    "          ret = ret + (s + e) * c // 2\n",
    "          k = k - c\n",
    "        s = n + 1\n",
    "      else:\n",
    "        e = s + k - 1\n",
    "        c = e - s + 1\n",
    "        ret = ret + (s + e) * c // 2\n",
    "        k = 0\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        maxv = 0\n",
    "        minus = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if i>0 and nums[i-1]==num:continue\n",
    "            if num-maxv-1>=k:\n",
    "                maxv += k\n",
    "                k=0\n",
    "                break\n",
    "            else:\n",
    "                k-=num-maxv-1\n",
    "                maxv = num\n",
    "                minus += num\n",
    "            print(k,maxv)\n",
    "        maxv+=k\n",
    "        return (1+maxv)*maxv//2 - minus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        nums.extend([0, inf])  # 加入两个哨兵\n",
    "        nums.sort()\n",
    "        for x, y in pairwise(nums):\n",
    "            fill = y - x - 1  # 可以填充的数字个数\n",
    "            if fill <= 0:  # 没有可以填充的位置\n",
    "                continue\n",
    "            if fill >= k:  # 填充剩余的 k 个数\n",
    "                return ans + (x * 2 + 1 + k) * k // 2  # 等差数列求和\n",
    "            ans += (x + y) * fill // 2  # 填充 fill 个数：等差数列求和\n",
    "            k -= fill  # 更新剩余要填充的数字个数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        n = len(nums)\n",
    "        res = idx = 0\n",
    "        pre = 1\n",
    "        for i in nums:\n",
    "            if pre < i:\n",
    "                if pre + k - 1 < i:\n",
    "                    res += (2*pre+k-1) * k // 2\n",
    "                    k = 0\n",
    "                    break\n",
    "                else:\n",
    "                    gap = i - pre \n",
    "                    res += (pre+i-1) * gap // 2 \n",
    "                    k -= gap\n",
    "            pre = i + 1\n",
    "            print(pre, i, res)\n",
    "        return res+(pre*2+k-1) * k // 2 if k else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        arr = [0]+sorted(nums)+[10**9+10]\n",
    "        ans = 0\n",
    "        def cal(st, t):\n",
    "            return (st+st+t-1)*t//2\n",
    "        print(arr)\n",
    "        for i in range(1, len(arr)):\n",
    "            t = min(k, arr[i]-arr[i-1]-1)\n",
    "            if t<0:\n",
    "                t = 0\n",
    "            ans += cal(arr[i-1]+1, t)\n",
    "            k -= t\n",
    "    \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums.append(0)\n",
    "        nums = sorted(list(set(nums)))\n",
    "        res = 0\n",
    "        for index in range(1, len(nums)):\n",
    "            if nums[index] - nums[index - 1] - 1 >= k:\n",
    "                res += (nums[index - 1] + 1 + nums[index - 1] + k) * k // 2\n",
    "                return res\n",
    "            else:\n",
    "                res += (nums[index - 1] + 1 + nums[index] - 1) * (nums[index] - nums[index - 1] - 1) // 2\n",
    "                k -= nums[index] - nums[index - 1] - 1\n",
    "\n",
    "        if k > 0:\n",
    "            res += (nums[-1] + 1 + nums[-1] + k) * k // 2\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, A: List[int], k: int) -> int:\n",
    "        ans = (1+k)*k//2\n",
    "        for v in sorted(set(A)):\n",
    "            if v <= k :\n",
    "                k+=1\n",
    "                ans += k-v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums = sorted(list(set(nums)))\n",
    "\n",
    "        ans = 0\n",
    "        if nums[0] > 1:\n",
    "            t = nums[0] - 1\n",
    "            t = min(t, k)\n",
    "            k -= t\n",
    "            ans += (1 + 1 + t - 1) * t // 2\n",
    "        \n",
    "        for x, y in pairwise(nums):\n",
    "            if y - x > 1:\n",
    "                a = x + 1\n",
    "                t = min(k, y - x - 1)\n",
    "                k -= t\n",
    "                b = a + t - 1\n",
    "                ans += (a + b) * t // 2\n",
    "\n",
    "            if not k:\n",
    "                break\n",
    "        \n",
    "        if k:\n",
    "            a = nums[-1] + 1\n",
    "            b = a + k - 1\n",
    "            ans += (a + b) * k // 2\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        # a = set(nums)\n",
    "        # b = []\n",
    "        # i = 1\n",
    "        # count = 0\n",
    "        # while i:\n",
    "        #     if i not in a:\n",
    "        #         b.append(i)\n",
    "        #         count += 1\n",
    "        #     i += 1\n",
    "        #     if count == k:\n",
    "        #         break\n",
    "        # return sum(b)\n",
    "\n",
    "\n",
    "        nums = sorted(set(nums))\n",
    "\n",
    "        # 初始化变量\n",
    "        total_sum = 0\n",
    "        previous = 0\n",
    "\n",
    "        # 遍历数组查找缺失的整数\n",
    "        for num in nums:\n",
    "            # 在当前数字和上一个数字之间查找缺失的整数\n",
    "            missing_count = min(num - previous - 1, k)\n",
    "            if missing_count > 0:\n",
    "                # 计算丢失的整数的和\n",
    "                total_sum += (previous + 1 + previous + missing_count) * missing_count // 2\n",
    "                k -= missing_count\n",
    "            if k == 0:\n",
    "                break\n",
    "            previous = num\n",
    "\n",
    "        # 如果还需要更多整数，则继续从最大值之后添加\n",
    "        if k > 0:\n",
    "            total_sum += (nums[-1] + 1 + nums[-1] + k) * k // 2\n",
    "\n",
    "        return total_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        ans = (k+1)*k//2\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] <= k:\n",
    "                k += 1\n",
    "                ans += k - nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        ss = list(set(nums))\n",
    "        ss.sort()\n",
    "        pres = 0\n",
    "        i = 0\n",
    "        while i < len(ss):\n",
    "            if ss[i] - i - 1 >= k:\n",
    "                break\n",
    "            pres += ss[i]\n",
    "            i += 1\n",
    "\n",
    "        t = ss[i-1] + k - (ss[i - 1] - i)\n",
    "        rst = t * (t + 1) // 2 - pres\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums=list(set(nums))\n",
    "        now=0\n",
    "        c=0\n",
    "        nums.sort()\n",
    "        for x in nums:\n",
    "            if x<=k:\n",
    "                k+=1\n",
    "                now+=x\n",
    "        return (k+1)*k//2-now\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        n = len(nums)\n",
    "        while i<n:\n",
    "            if k + i + 1< nums[i]:\n",
    "                break \n",
    "            i += 1\n",
    "  \n",
    "        if i==n:\n",
    "            return (k+n) *(k+n+1)//2 - sum(nums)\n",
    "        else:\n",
    "            return (k+i) *(k+i+1)//2 - sum(nums[:i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimalKSum(self, nums: List[int], k: int) -> int:\n",
    "        ans = (1 + k) * k // 2\n",
    "        d = set()\n",
    "        for i in nums:\n",
    "            if i <= k and i not in d:\n",
    "                ans -= i\n",
    "                k += 1\n",
    "                while k in d:\n",
    "                    k += 1\n",
    "                ans += k\n",
    "            d.add(i)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
